PGCD et algorithme d'Euclide - Corrigé

Énoncé

  Utiliser l'algorithme d'Euclide pour calculer le PGCD des nombres suivants.

1. \(255\) et \(189\)

2. \(1\,260\) et \(3\,234\)

3. \(8\,008\) et \(4\,095\)

4. \(783\) et  \(1\,395\)

Solution

1. On utilise l'algorithme d'Euclide :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 255& 189& 1& 66\\ \hline 189& 66& 2& 57\\ \hline 66& 57& 1& 9\\ \hline 57& 9& 6& 3\\ \hline 9& 3& 3& 0\\ \hline\end{array}\end{align*}\)  

donc \(\mathrm{PGCD}(255;189)=3\) .

2. On utilise l'algorithme d'Euclide :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 3\,234& 1\,260& 2& 714\\ \hline 1\,260& 714& 1& 546\\ \hline 714& 546& 1& 168\\ \hline 546& 168& 3& 42\\ \hline 168& 42& 4& 0\\ \hline\end{array}\end{align*}\)  

donc \(\mathrm{PGCD}(1\,260;3\,234)=42\) .

3. On utilise l'algorithme d'Euclide :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 8\,008& 4\,095& 1& 3\,913\\ \hline 4\,095& 3\,913& 1& 182\\ \hline 3\,913& 182& 21& 91\\ \hline 182& 91& 2& 0\\ \hline\end{array}\end{align*}\)  

donc \(\mathrm{PGCD}(8\,008;4\,095)=91\) .

4. On utilise l'algorithme d'Euclide :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 1\,395& 783& 1& 612\\ \hline 783& 612& 1& 171\\ \hline 612& 171& 3& 99\\ \hline 171& 99& 1& 72\\ \hline 99& 72& 1& 27\\ \hline 72& 27& 18& 9\\ \hline 27& 9& 3& 0\\ \hline\end{array}\end{align*}\)  

donc \(\mathrm{PGCD}(783;1\,395)=9\) .